from typing import List


class Solution:
    def bubbleSort(self, nums: List[int]) -> None:
        "冒泡排序,比较排序,交换位置,时间复杂度平方级,空间复杂度常数级,比小或者比大,稳定"
        n = len(nums)
        for i in range(n - 1):
            for j in range(n - i - 1):
                if nums[j + 1] < nums[j]:
                    nums[j], nums[j + 1] = nums[j + 1], nums[j]

        print(nums)

    def selectionSort(self, nums: List[int]) -> None:
        "选择排序,比较排序,交换位置,时间复杂度平方级,空间常数级,每一次排序找出最大/小值跟第一个/最后一个值交换位置,剩下元素继续选择排序,不稳定"
        n = len(nums)
        for i in range(n - 1):
            min_index = i
            for j in range(i + 1, n):
                if nums[j] < nums[min_index]:
                    min_index = j
            nums[i], nums[min_index] = nums[min_index], nums[i]
        print(nums)

    def insertionSort(self, nums: List[int]) -> None:
        "插入排序,分已排序和未排序,假设第一个元素为已排序,则二到最后为未排序,从未排序依次拿元素插入到已排序中,从后往前比较,不断地挪位置,时间复杂度平方级,空间复杂度常数级,稳定"
        for i in range(len(nums)):
            pre_index = i - 1
            current = nums[i]
            while pre_index >= 0 and nums[pre_index] > current:
                nums[pre_index + 1] = nums[pre_index]
                pre_index -= 1
            nums[pre_index + 1] = current
        print(nums)

    def shellSort(self, nums: List[int]) -> None:
        "希尔排序,插入排序的进阶版本,通过gap不断地分组排序,把较大/小值堆在后面,减少插入排序时候的交换次数,最后gap=1时候完全排序"
        n = len(nums)
        gap = n // 2
        #  假设gap=2, [2, 9,   4, 3,   10,6,   5, 8,    7, 1]
        while gap > 0:
            for i in range(gap, n):
                j = i
                while j > 0:
                    if nums[j] < nums[j - gap]:
                        # swap
                        nums[j], nums[j - gap] = nums[j - gap], nums[j]
                        j = j - gap
                    else:
                        # 因为前面的已经排好序了,不需要往前比较了
                        break
            gap = gap // 2
        print(nums)


if __name__ == '__main__':
    s = Solution()
    nums = [2, 9, 4, 3, 10, 6, 5, 8, 7, 1]
    # s.bubbleSort(nums)
    # s.selectionSort(nums)
    # s.insertionSort(nums)
    s.shellSort(nums)
